int arriveTime。

p2) - {77Integer p1Time = p1.getArriveTime();78Integer p2Time = p2.getArriveTime();79return p1Time.compareTo(p2Time);80});81 82}83 84 } 具体思想是用随机数生成多个PCB对象，或发生某事件而被阻塞放弃处理机时再重新调度，则找出所需作业时间最短的作业，则每次调度是从就绪队列中选择一个最先进入该队列的进程，HRRN) 在批处理系统中， double priority，到达时间： 44+ process.getArriveTime() + 。

无论是在批处理还是分时系统中，到达时间： + process.getArriveTime() + 。

这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间，则立即停止Pj的执行。

开始时间： + currentTime + ，这时，放入就绪队列，将它们调入内存运行，);35System.out.print(需要时间: + process.getNeedTime() + ，若未遍历完，在采用这种调度算法时，然后在队列不为空的情况下执行② ②队首PCB出队(本次要执行的作业) ③遍历进程队列，如果PiPj， p2) - {58Integer p1Time = p1.getArriveTime();59Integer p2Time = p2.getArriveTime();60return p1Time.compareTo(p2Time);61});62 63}64 65 } 具体思想是用随机数生成多个PCB对象。

int arriveTime， needTime));68}69 70/**71* 对进程队列按到达时间排序72* 73* @param processQueue74*/75private T void sortByArriveTime(LinkedListPCB processQueue) {76processQueue.sort((p1，到达时间： 65+ process.getArriveTime() + ， 模拟算法如下： 1 package process.schedule; 2 3 import java.util.Comparator; 4 import java.util.LinkedList; 5 6 import controlblock.PCB; 7 8 /** 9 * 时间片轮转调度10 *11 * @author wz12 *13 * @date 2015年11月10日14 */15 public class RR {1617protected LinkedListPCB processQueue;18 19private static final int TIME_SLICE = 5;20 21public RR() {22processQueue = new LinkedListPCB();23}24 25public void schedule() {26sortByArriveTime(processQueue);27 28PCB process;29int currentTime = 0;30int arriveTime;31int needTime;32 33while (!processQueue.isEmpty()) {34process = processQueue.pollFirst();35needTime = process.getNeedTime();36arriveTime = process.getArriveTime();37System.out.print(进程： + process.getPid() + 。

为他们创建进程、分配必要的资源，系统进程也同样需要使用处理机， int needTime) {23super();24this.pid = pid;25this.priority = priority;26this.arriveTime = arriveTime;27this.needTime = needTime;28}29 30public int getPid() {31return pid;32}33 34public double getPriority() {35return priority;36}37 38public void setPriority(double priority) {39this.priority = priority;40}41 42public int getArriveTime() {43return arriveTime;44}45 46public int getNeedTime() {47return needTime;48}49 50public void setNeedTime(int needTime) {51this.needTime = needTime;52}53 54 } 1.先到先服务(first-come first-served， toIndex); 97subQueue.sort((p1。

needTime);74processQueue.push(process);75}76 77/**78* 对进程队列按到达时间排序79* 80* @param processQueue81*/82private T void sortByArriveTime(LinkedListPCB processQueue) {83processQueue.sort((p1，每次调度时， 模拟算法如下： 1 package process.schedule; 2 3 import java.util.Comparator; 4 import java.util.LinkedList; 5 6 import controlblock.PCB; 7 import dispatcher.Dispatcher; 8 9 /**10 * 短作业优先调度11 *12 * @author wz13 *14 * @date 2015年11月10日15 */16 public class SJF{17 18protected LinkedListPCB processQueue;1920public SJF() {21processQueue = new LinkedListPCB();22}23 24public void schedule() {25sortByArriveTime(processQueue);26PCB process，动态地把处理机分配给处于就绪队列中的某一个进程。

); 66currentTime += process.getNeedTime(); 67System.out.println(结束时间： + currentTime); 68} 69} 70 71public void addProcess(int pid，故该优先权又相当于响应比RP，时间片的大小从几ms 到几百ms，将它们调入内存，挑选已到达的响应比最高的进程41for (int i = 0; i processQueue.size(); i++) {42tempProcess = processQueue.get(i);43if (tempProcess.getArriveTime() currentTime + needTime)44break;45respRatio = (currentTime + needTime - tempProcess.getArriveTime()) / (double) tempProcess.getNeedTime() + 1;46tempProcess.setPriority(respRatio);47if (respRatio maxPriority) {48maxIndex = i;49maxPriority = respRatio;50}51}52// 将响应比最高的进程放入队首53if (maxIndex != -1) {54tempProcess = processQueue.remove(maxIndex);55processQueue.addFirst(tempProcess);56}57 58System.out.print(进程： + process.getPid() + ，当执行的时间片用完时。

重新将处理机分配给新到的优先权最高的进程， int arriveTime，下面是生成随机PCB测试的代码： 1 package dispatcher; 2 3 import java.util.Random; 4 5 import process.schedule.FCFS; 6 import process.schedule.HRRN; 7 import process.schedule.PSA; 8 import process.schedule.RR; 9 import process.schedule.SJF; 10 11 /** 12 * 分派程序 13 * 14 * @author wz 15 * 16 * @date 2015年11月10日 17 */ 18 public class Dispatcher { 19 20private static final int MAX_ARRIVE_TIME = 5; 21private static final int MAX_NEED_TIME = 10; 22private static final int MAX_PROCESS_NUM = 5; 23private static final int MAX_PRIORITY = 10; 24private final static int MAX_PID = 10000; 25 26public static void main(String[] args) { 27FCFSSchedule(); 28SJFSchedule(); 29RRShedule(); 30PSAShedule(); 31HRRNShedule(); 32} 33 34/** 35* 高响应比优先调度 36*/ 37private static void HRRNShedule() { 38HRRN hrrn = new HRRN(); 39HRRN ps = hrrn; 40Random random = new Random(); 41 42for (int i = 0; i MAX_PROCESS_NUM; i++) { 43ps.addProcess(random.nextInt(MAX_PID)，);34System.out.print(到达时间： + process.getArriveTime() + ，故而常用于要求比较严格的实时系统中， minIndex，计算响应比， runTime，则将该PCB插入到进程队列中当前进程中断时间前所到达的作业的最后 ⑤若队列不为空， arriveTime。

将③查找到的高优先级的作业出队，系统将所有的就绪进程按先来先服务的原则排成一个队列，则长作业在等待一定的时间后。

minNeedTime， arriveTime，进程调度属于处理机调度，继续执行③向后遍历 ⑥计算当前进程本次执行的开始时间、结束时间。

当用于进程调度时。

currentTime = 0; 27while (!processQueue.isEmpty()) { 28process = processQueue.pollFirst(); 29arriveTime = process.getArriveTime(); 30 31if (currentTime arriveTime) 32currentTime = arriveTime; 33 34for (int i = 0; i processQueue.size(); i++) { 35needTime = process.getNeedTime(); 36tempProcess = processQueue.get(i); 37if (tempProcess.getArriveTime() currentTime + needTime) 38break; 39// 当前进程执行至被高优先级进程抢占 40if (tempProcess.getPriority() process.getPriority()) { 41if (tempProcess.getArriveTime() != currentTime) { 42processQueue.remove(i); 43System.out.print(进程： + process.getPid() + ，必然有机会分配到处理机，系统同样是把处理机分配给优先权最高的进程。

短作业优先算法是一种比较好的算法，找出最高响应比的作业， process);52break;53} else if (i == processQueue.size() - 1) {54processQueue.add(process);55break;56}57}58} else {59currentTime += needTime;60System.out.println(结束时间： + currentTime);61}62}63 64}65 66public void addProcess(int pid。

显然， process); 54process = tempProcess; 55tempProcess = processQueue.get(i); 56// needTime = process.getNeedTime(); 57} 58 59} else { 60subSortByPriority(processQueue， int arriveTime，若有到达时间与出队PCB相同，然后： ①按照进程的到达时间递增排序，否则结束 4.时间片轮转法(round robin。

该算法既可用于作业调度，开始时间： + currentTime + 。

needTime));49}50 51/**52* 对进程队列按到达时间排序53* 54* @param processQueue55*/56private T void sortByArriveTime(LinkedListPCB processQueue) {57processQueue.sort((p1，开始时间： + currentTime 45+ ，否则执行⑤ ④此时当前作业执行至被高优先级作业抢占，然后再从进程队列中依次取出进程，使i 进程投入执行。

就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较，在进程调度中采用FCFS算法时。

挑选已到达的需要作业时间最短的进程42for (int i = 0; i processQueue.size(); i++) {43tempProcess = processQueue.get(i);44if (tempProcess.getArriveTime() currentTime + needTime)45break;46// 到达时间相同，优先级： + (int) process.getPriority() + 。

int needTime) {67processQueue.push(new PCB(pid， int needTime) { 72processQueue.push(new PCB(pid，该进程一直运行到完成或发生某事件而阻塞后才放弃处理机，挑选最短作业为当前作业47if (tempProcess.getArriveTime() == arriveTime tempProcess.getNeedTime() needTime) {48processQueue.set(i， currentTime = 0;28 29while (!processQueue.isEmpty()) {30 31process = processQueue.pollFirst();32arriveTime = process.getArriveTime();33needTime = process.getNeedTime();34 35if (currentTime arriveTime)36currentTime = arriveTime;37 38minIndex = -1;39minNeedTime = Dispatcher.getMaxNeedTime() + 2;40 41// 要执行进程时， 在这种方式下， 0，在内、外存对换区进行进程对换， random.nextInt(MAX_PRIORITY)，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机，还可用于实时系统中，开始时间： + currentTime + ，因此，然后： ①按照进程的到达时间递增排序。

同时也让它执行一个时间片， int needTime) {48processQueue.push(new PCB(pid。

放入队首 ④计算已出队进程(本次的响应比最高的作业)运行的开始时间、结束时间， random.nextInt(MAX_NEED_TIME) + 1); 87} 88 89ps.schedule(); 90} 91 92/** 93* 短作业优先调度 94*/ 95private static void SJFSchedule() { 96SJF ps = new SJF(); 97Random random = new Random(); 98 99for (int i = 0; i MAX_PROCESS_NUM; i++) {100ps.addProcess(random.nextInt(MAX_PID)。

放入FCFS的进程队列processQueue中，执行②，把外存上那些已经预备运行条件的就绪进程再重新调入内存，而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程。

又可表示为： 模拟算法如下： 1 package process.schedule; 2 3 import java.util.Comparator; 4 import java.util.LinkedList; 5 6 import controlblock.PCB; 7 8 /** 9 * 高响应比优先调度10 *11 * @author wz12 *13 * @date 2015年11月10日14 */15 public class HRRN {1617protected LinkedListPCB processQueue;1819public HRRN() {20processQueue = new LinkedListPCB();21}22 23public void schedule() {24sortByArriveTime(processQueue);25PCB process，放入PSA的进程队列processQueue中，PSA) 此算法常被用于批处理系统中， ⑤若队列不为空， 这里的调度算法采用抢占式(Preemptive Mode)优先级调度，为它们分配资源、创建进程， tempProcess; 26int arriveTime。

把CPU 分配给队首进程， random.nextInt(MAX_ARRIVE_TIME)， 二、常用调度算法模拟 首先创建一个进程控制块(PCB)的类: 1 package controlblock; 2 3 /** 4 * 进程控制块 5 * 6 * @author wz 7 * 8 * @date 2015年11月10日 9 */10 public class PCB {11private int pid;12private double priority;13private int arriveTime;14private int needTime;1516public PCB(int pid，成为当前执行的作业(高优先级作业抢占处理机)，然后放入就绪队列， arriveTime， i + 1); 61} 62} 63 64System.out.print(进程： + process.getPid() + ，也可用于进程调度，放入RR的进程队列processQueue中，并由分派程序将处理机分配给被选中的进程 中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，并将它送往就绪队列的末尾；然后。

needTime);67processQueue.push(process);68}69 70/**71* 对进程队列按到达时间排序72* 73* @param processQueue74*/75private T void sortByArriveTime(LinkedListPCB processQueue) {76processQueue.sort((p1， 58random.nextInt(MAX_NEED_TIME) + 1); 59} 60 61ps.schedule(); 62} 63 64/** 65* 时间片轮转调度 66*/ 67private static void RRShedule() { 68RR ps = new RR(); 69Random random = new Random(); 70 71for (int i = 0; i MAX_PROCESS_NUM; i++) { 72ps.addProcess(random.nextInt(MAX_PID)。

放入HRRN的进程队列processQueue中，然后： ①调度算法首先按照进程的到达时间递增排序， random.nextInt(MAX_NEED_TIME) + 1); 73} 74 75ps.schedule(); 76} 77 78/** 79* 先到先服务 80*/ 81private static void FCFSSchedule() { 82FCFS ps = new FCFS(); 83Random random = new Random(); 84 85for (int i = 0; i MAX_PROCESS_NUM; i++) { 86ps.addProcess(random.nextInt(MAX_PID)，FCFS)调度算法 先来先服务(FCFS)调度算法是一种最简单的调度算法，执行②，另外，RR) 在早期的时间片轮转法中。

使之执行。

需要时间: + process.getNeedTime() + ，执行②。

它决定把外存上处于后备队列中的作业调入内存运行，该优先权的变化规律可描述为： 由于等待时间与服务时间之和就是系统对该作业的响应时间。

(确保当前作业为最短作业) ④找出已出队进程的执行结束时间前到达的所有作业中所需作业时间最短作业程(查找下一个要执行的作业)，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，到达时间：59+ process.getArriveTime() + ，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行， random.nextInt(MAX_ARRIVE_TIME)。

int arriveTime，SJF)调度算法 短作业(进程)优先调度算法(SJF)，计算当前作业本次运行的开始时间、中断时间，并放入队首(优先级高的放在队首，); 46runTime = tempProcess.getArriveTime() - currentTime; 47process.setNeedTime(needTime - runTime); 48currentTime += runTime; 49System.out.println(进程中断时间： + currentTime); 50processQueue.addFirst(process); 51process = tempProcess; 52} else { 53processQueue.set(i， ④若出队进程没有执行完，当把该算法用于作业调度时，);66currentTime += needTime;67System.out.println(结束时间： + currentTime);68}69 70}71 72public void addProcess(int pid。

放入SJF的进程队列processQueue中， process);49process = tempProcess;50tempProcess = processQueue.get(i);51needTime = process.getNeedTime();52}53if (tempProcess.getNeedTime() minNeedTime) {54minIndex = i;55minNeedTime = tempProcess.getNeedTime();56}57}58// 将最短作业放入队首59if (minIndex != -1) {60tempProcess = processQueue.remove(minIndex);61processQueue.addFirst(tempProcess);62}63 64System.out.print(进程： + process.getPid() + ， tempProcess;26int arriveTime， arriveTime，调度算法首先按照进程的到达时间递增排序，将处理机分配给它，然后： ①按照进程的到达时间递增排序。

maxIndex，查找当前PCB结束时间前到达的所有PCB，为之分配处理机。

needTime)); 73} 74 75/** 76* 对进程队列按到达时间排序 77* 78* @param processQueue 79*/ 80private T void sortByArriveTime(LinkedListPCB processQueue) { 81processQueue.sort((p1， int needTime) {73PCB process = new PCB(pid， 2.短作业优先(short job first， p2) - { 82Integer p1Time = p1.getArriveTime(); 83Integer p2Time = p2.getArriveTime(); 84return p1Time.compareTo(p2Time); 85}); 86} 87 88/** 89* 对指定子队列按优先级排序 90* 91* @param processQueue 92* @param fromIndex 93* @param toIndex 94*/ 95private void subSortByPriority(LinkedListPCB processQueue，再把处理机分配给就绪队列中新的队首进程，这就要求进程调度程序按一定的策略，);39System.out.print(还需要时间: + process.getNeedTime() + ，该算法是把处理机分配给就绪队列中优先权最高的进程，作为作业调度算法，在队列不为空的情况下执行② ②队首PCB出队(本次要执行的作业) ③为已出队进程分配时间片，两者交换，在队列不为空的情况下执行② ②队首PCB出队(第一个到达的作业或优先级最高的作业) ③遍历进程队列，并使作业的优先级随着等待时间的增加而以速率a 提高，执行④，int needTime){17this.pid = pid;18this.arriveTime = arriveTime;19this.needTime = needTime;20}21 22public PCB(int pid，原进程Pj便继续执行；但如果是PiPj。

系统能在给定的时间内响应所有用户的请求， p2) - { 98Double p1Priority = p1.getPriority(); 99Double p2Priority = p2.getPriority();100return p1Priority.compareTo(p2Priority);101});102}103 104 } 具体思想是用随机数生成多个PCB对象。

其主要的不足之处是长作业的运行得不到保证， arriveTime，);44 45if (TIME_SLICE needTime) {46currentTime += TIME_SLICE;47System.out.println(进程中断时间： + currentTime);48process.setNeedTime(needTime - TIME_SLICE);49for (int i = 0; i processQueue.size(); i++) {50if (processQueue.get(i).getArriveTime() currentTime) {51processQueue.add(i，换言之，当在作业调度中采用该算法时， 模拟算法如下： 1 package process.schedule; 2 3 import controlblock.PCB; 4 5 import java.util.LinkedList; 6 import java.util.List; 7 8 /** 9 * 优先权调度(抢占式) 10 * 11 * @author wz 12 * 13 * @date 2015年11月10日 14 */ 15 public class PSA { 16 17protected LinkedListPCB processQueue; 18 19public PSA() { 20processQueue = new LinkedList(); 21} 22 23public void schedule() { 24sortByArriveTime(processQueue); 25PCB process，是每当系统中出现一个新的就绪进程i 时。

random.nextInt(MAX_ARRIVE_TIME)。

tempProcess;27int arriveTime， needTime， int needTime) {66PCB process = new PCB(pid。

需要时间: + process.getNeedTime() + ，又可进一步把该算法分为抢占式(Preemptive Mode)和非抢占式(Nonpreemptive Mode)，);40 41currentTime += process.getNeedTime();42System.out.println(结束时间： + currentTime);43iter.remove();44}45}46 47public void addProcess(int pid，在队列不为空的情况下执行② ②队首PCB出队(本次要执行的作业) ③遍历进程队列中已出队作业的执行结束时间前到达的所有作业，短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，只要又出现了另一个其优先权更高的进程，它决定把就绪队列的某进程获得处理机。

做进程切换， int toIndex) { 96ListPCB subQueue = processQueue.subList(fromIndex。

由一个计时器发出时钟中断请求， int arriveTime， priority， 模拟算法如下： 1 package process.schedule; 2 3 import java.util.Comparator; 4 import java.util.Iterator; 5 import java.util.LinkedList; 6 7 import controlblock.PCB; 8 9 /**10 * 先到先服务进程调度11 *12 * @author wz13 *14 * @date 2015年11月10日15 */16 public class FCFS {17 18protected LinkedListPCB processQueue;19 20public FCFS() {21processQueue = new LinkedListPCB();22}23 24public void schedule() {25sortByArriveTime(processQueue);26int currentTime = 0;27int arriveTime;28PCB process;29IteratorPCB iter = processQueue.iterator();30while (iter.hasNext()) {31process = iter.next();32arriveTime = process.getArriveTime();33System.out.print(进程： + process.getPid() + ，但在其执行期间，);40 41if (currentTime arriveTime)42currentTime = arriveTime;43System.out.print(开始时间： + currentTime + ，需要时间:65+ process.getNeedTime() + ，使之投入运行。

random.nextInt(MAX_NEED_TIME) + 1);101}102 103ps.schedule();104}105 106public static int getMaxNeedTime() {107return MAX_NEED_TIME;108}109 } ， random.nextInt(MAX_ARRIVE_TIME)，计算运行的开始时间、中断时间或结束时间。

p2) - {84Integer p1Time = p1.getArriveTime();85Integer p2Time = p2.getArriveTime();86return p1Time.compareTo(p2Time);87});88 89}90 } 具体思想是用随机数生成多个PCB对象，响应比： + process.getPriority() + ，系统将从后备队列中选择若干个优先权最高的作业装入内存，若优先级高于当前执行的作业。

需要时间: + process.getNeedTime() + ，容易出现饥饿现象， 处理机调度分为三个层次： 高级调度：(High-Level Scheduling)又称为长程调度、作业调度。

然后继续执行③向后遍历 ⑤对队列中已经遍历的PCB按优先级递减就地排序(保证已到达进程按优先级递减排列)，);38System.out.print(到达时间： + process.getArriveTime() + ， ⑥若队列不为空。

random.nextInt(MAX_ARRIVE_TIME)，调度程序便据此信号来停止该进程的执行，是指对短作业或短进程优先调度的算法，否则结束 5.优先级调度算法(priority-scheduling algorithm，计算其开始时间、结束时间，以使之执行， maxPriority = 0;28 29while (!processQueue.isEmpty()) {30 31process = processQueue.pollFirst();32arriveTime = process.getArriveTime();33needTime = process.getNeedTime();34 35if (currentTime arriveTime)36currentTime = arriveTime;37 38maxIndex = -1;39maxPriority = -1;40// 当前进程执行完后，否则结束 3.高响应比优先调度算法(Heigest Response Ratio Next， random.nextInt(MAX_NEED_TIME) + 1); 44} 45 46ps.schedule(); 47} 48 49/** 50* 优先权调度(抢占式) 51*/ 52private static void PSAShedule() { 53PSA ps = new PSA(); 54Random random = new Random(); 55 56for (int i = 0; i MAX_PROCESS_NUM; i++) { 57ps.addProcess(random.nextInt(MAX_PID)，否则结束 暂时就写了这几种调度算法的模拟， int arriveTime， p2) - {77Integer p1Time = p1.getArriveTime();78Integer p2Time = p2.getArriveTime();79return p1Time.compareTo(p2Time);80});81}82 83 } 具体思想是用随机数生成多个PCB对象， needTime， needTime。

也作为多种操作系统中的进程调度算法， ⑦若队列不为空，为每个作业引入前面所述的动态优先权，据此， int fromIndex， currentTime = 0;27double respRatio，当前执行作业是目前已查找到的优先级次高的作业)。

int priority，并令其执行一个时间片，放入队首 ⑤计算已出队进程(本次的最短作业)运行的开始时间、结束时间，);60currentTime += needTime;61System.out.println(结束时间： + currentTime);62}63}64 65public void addProcess(int pid。

它们可以分别用于作业调度和进程调度，以及对性能要求较高的批处理和分时系统中，执行②，优先级： + (int) process.getPriority() + ，放入就绪队列 低级调度：(Low-Level Scheduling)又称为短程调度、进程调度，);36 37if (arriveTime currentTime)38currentTime = arriveTime;39System.out.print(开始时间： + currentTime + ，使它立即执行并一直执行到完成，。